package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/3 9:08
 * @description：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/
 */
public class K次取反后最大化的数组和 {
    @Test
    public void test() {
        Solution solution = new Solution();
        // System.out.println(solution.binary_search(new int[]{-2, -1, 0, 0, 0, 0, 0}, 0));
        System.out.println(solution.largestSumAfterKNegations(new int[]{8, -7, -3, -9, 1, 9, -6, -9, 3}, 8));
    }

    /*
    class Solution {
        public int largestSumAfterKNegations(int[] nums, int k) {
            Arrays.sort(nums);
            int index_0 = binary_search(nums, 0);
            // 找出负数的个数
            int negativeNums = index_0 + 1;
            if (negativeNums <= k) { // 如果负数的个数小于k
                // 先将所有负数转为正数
                k -= negativeNums;
                for (int i = 0; i < negativeNums; i++) {
                    nums[i] = -nums[i];
                }
                if (k % 2 != 0) { // 如果剩余的反转次数为奇数
                    // 找到最小的数，反转一次即可
                    if (index_0 + 1 < nums.length && nums[index_0] > nums[index_0 + 1]) {
                        index_0++;
                    }
                    nums[index_0] = -nums[index_0];
                }
            } else { // 负数的个数大于k
                // 反转较小的负数即可
                for (int i = 0; i < k; i++) {
                    nums[i] = -nums[i];
                }
            }
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
            }
            return sum;
        }

        private int binary_search(int[] nums, int tar) {
            int l = 0;
            int r = nums.length - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (tar > nums[mid]) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            return l;
        }
    }
     */

    class Solution {
        public int largestSumAfterKNegations(int[] nums, int k) {
            int n = nums.length, min_idx = 0;
            boolean zero = false;
            PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(a -> nums[a]));
            for (int i = 0; i < n; i++) {
                if (nums[i] < 0) queue.offer(nums[i]);
                if (nums[i] == 0) zero = true;
                if (nums[i] < nums[min_idx]) min_idx = i;
            }
            if (k <= queue.size()) {
                while (k-- > 0) nums[queue.peek()] = -nums[queue.poll()];
            } else {
                while (!queue.isEmpty() && k-- > 0) nums[queue.peek()] = -nums[queue.poll()];
                if (!zero && k % 2 != 0) nums[min_idx] = -nums[min_idx];
            }
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            return sum;
        }
    }

}
